Grover's search algorithm can be applied to a wide range of problems; evenproblems not generally regarded as searching problems, can be reformulated totake advantage of quantum parallelism and entanglement, and lead to algorithmswhich show a square root speedup over their classical counterparts. In this paper, we discuss a systematic way to formulate such problems andgive as an example a quantum scheduling algorithm for an $R||C_{max}$ problem.$R||C_{max}$ is representative for a class of scheduling problems whose goal isto find a schedule with the shortest completion time in an unrelated parallelmachine environment. Given a deadline, or a range of deadlines, the algorithm presented in thispaper allows us to determine if a solution to an $R||C_{max}$ problem with $N$jobs and $M$ machines exists, and if so, it provides the schedule. The timecomplexity of the quantum scheduling algorithm is $\mathcal{O}(\sqrt{M^N})$while the complexity of its classical counterpart is $\mathcal{O}(M^N)$.
展开▼
机译：Grover的搜索算法可以应用于各种问题。即使是通常不被认为是搜索问题的问题，也可以重新构造以利用量子并行性和纠缠的优势，并导致算法显示出比传统算法更快的平方根。在本文中，我们讨论了一种系统的表达此类问题的方法，并以$ R || C_ {max} $问题的量子调度算法为例。$ R || C_ {max} $代表一类调度目的是在不相关的并行机环境中找到具有最短完成时间的计划的问题。给定一个截止日期或一个截止日期范围，本文介绍的算法使我们能够确定是否存在$ N $ jobs和$ M $机器的$ R || C_ {max} $问题的解决方案，如果存在，它提供了时间表。量子调度算法的时间复杂度为$ \ mathcal {O}（\ sqrt {M ^ N}）$，而其经典对应算法的复杂度为$ \ mathcal {O}（M ^ N）$。
展开▼
